package leetcode_81_100;

import java.util.Deque;
import java.util.LinkedList;

public class maximalRectangle_85 {
    /**
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵
     * 找出只包含 1 的最大矩形，并返回其面积。
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        /**
         * 遍历判断每一个1，以这些1为矩形左上角进行计算
         *  必然有大量包含在其他矩形中的1没有必要计算，需要对其判断
         */
        int maxArea=0 , row=matrix.length,col=matrix[0].length;
        boolean[][] used=new boolean[row][col];//没有必要计算的1，赋值true
        for (int i = 0; i < row; i++)
            for (int t = 0; t < col; t++) {
                if (!used[i][t]) {
                    int area = 0;
                    if (matrix[i][t] == '1')
                        area = area(i, t, matrix, used);
                    if (area > maxArea)
                        maxArea = area;
                }
            }
        return maxArea;
    }

    public int area(int row,int col,char[][] matrix,boolean[][] used){
        int width, height = 0,lastWidth=matrix[0].length,maxArea=0;
        for (int i = row; i < matrix.length; i++) {
            int area=0;
            width=0;
            if (matrix[i][col] == '1') {
                height++;
                for (int t = col; t < matrix[0].length; t++) {
                    if (width < lastWidth && matrix[i][t] == '1'){   //下边的宽度不能大于上边的宽度
                        width++;
                        //进行判断，如果右边和下边是0，这个1之后就无需计算了
                        if(t!=matrix[0].length-1 && i!=matrix.length-1)
                            if (matrix[i][t + 1] == '0' && matrix[i + 1][t] == '0')
                                used[i][t] = true;
                    }
                    else
                        break;
                }
                lastWidth = width;
                area= lastWidth*height;
                if(area>maxArea)
                    maxArea=area;
            }else
                break;
        }
        return maxArea;
    }


    /**
     * 官解解法，单调栈求每一列上穿过该列的最大的矩形
     * 时间复杂度：O(mn)
     * 11ms,70%
     * @param matrix
     * @return
     */
    public int maximalRectangle2(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        // left[i][j]为矩阵第 i 行第 j 列元素的左边到自己，连续 1 的数量。
        int[][] left = new int[m+2][n];
        for (int i = 0; i < m+2; i++) {
            if (i != 0 && i != m + 1) //每一列的开头结尾设为0，便于后边单调栈的使用
                for (int j = 0; j < n; j++) {
                    if (matrix[i - 1][j] == '1')
                        left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
        int area = 0;
        //对于矩阵中任意一个点，我们枚举以该点为右下角的全 1 矩形。寻找组成的所有矩形的面积最大值
        // 此时对于left数组的每一列，经过处理可以看作是竖着的柱状图
        // 使用基于84题柱状图单调栈的方法求出每一列上最大的矩形面积
        for (int j = 0; j < n; j++) {
            // 对栈中柱体来说，栈中的前一个柱体就是其「上边第一个小于自身的柱体」；
            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < m+2; i++) {
                // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
                while (!stack.isEmpty() && left[i][j] < left[stack.peek()][j]  ) {
                    int h = left[stack.pop()][j];  //将栈顶元素出栈
                    area = Math.max(area, (i - stack.peek() - 1) * h); // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积
                }
                stack.push(i); //存入坐标
            }
        }
        return area;
    }

}
